package leetcode.code0312;

/**
 * 记忆化搜索 No.2 <br>
 * 修改递归语义
 * @author CaoYu
 * @date 2021年10月3日
 * @description
 */
public class Solution2 extends Solution312 {

	@Override
	public int maxCoins(int[] nums) {
		int n = nums.length;
		int[] pre = new int[n + 2];
		pre[0] = 1;
		pre[n + 1] = 1;
		Integer[][] dp = new Integer[n + 1][n + 1];
		for (int i = 0; i < n; i++) {
			pre[i + 1] = nums[i];
		}
		return f(pre, 1, n, dp);
	}

	public int f(int[] nums, int l, int r, Integer[][] dp) {
		if (dp[l][r] != null)
			return dp[l][r];
		if (l == r) {
			dp[l][r] = nums[l - 1] * nums[l] * nums[l + 1];
			return dp[l][r];
		}
		int max = f(nums, l + 1, r, dp) + nums[l] * nums[l - 1] * nums[r + 1];
		max = Math.max(max, f(nums, l, r - 1, dp) + nums[r] * nums[l - 1] * nums[r + 1]);
		for (int i = l + 1; i < r; i++) {
			max = Math.max(max, f(nums, l, i - 1, dp) + f(nums, i + 1, r, dp) + nums[i] * nums[l - 1] * nums[r + 1]);
		}
		dp[l][r] = max;
		return max;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
		so.debug5();
	}

}
